package com.gxc.tree;

import java.util.Stack;

/**
 * 树的中序遍历
 */
public class Inorder {

    public static void main(String[] args) {
        TreeBean tree = Preorder.createTree();

        //递归实现中序遍历
        recursion(tree);

        System.out.println("----------");
        Stack<TreeBean> stack = new Stack<>();
        nonRecursion(tree, stack);
    }

    /**
     * 非递归实现中序遍历
     * @param stack
     */
    private static void nonRecursion(TreeBean treeBean, Stack<TreeBean> stack) {
        while (treeBean!=null || !stack.empty()) {
            if (treeBean!=null) {
                stack.push(treeBean);
                treeBean = treeBean.left;
            } else {
                treeBean = stack.pop();
                System.out.print(treeBean.value + "  ");
                treeBean = treeBean.right;
            }
        }

    }

    /**
     * 递归实现中序遍历
     * @param tree
     */
    private static void recursion(TreeBean tree) {
        if (tree == null) return;

        recursion(tree.left);
        System.out.print(tree.value + "  ");
        recursion(tree.right);
    }
}
